/*
Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
*/

class Solution {
public:
    int singleNumber(int A[], int n) {
        const int sz = sizeof(int)*8;
        vector<int> bitcount(sz, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < sz; j++) {
                // check if A[i] has '1' on jth bit
                if (A[i] & (1<<j)) bitcount[j]++;
            }
        }
        int number = 0;
        for (int j = 0; j < sz; j++) {
            bitcount[j] %= 3;
            if (bitcount[j]) number |= (1<<j);
        }
        return number;
    }
};

#if 0
class Solution {
public:
    int singleNumber(int A[], int n) {
        double sum = 0;
        unordered_set<int> Ahelper;
        for (int i = 0; i < n; i++) {
            auto res = Ahelper.insert(A[i]);
            if (res.second) sum = sum + A[i] + A[i];
            else sum -= A[i];
        }
        sum = sum/2;
        return (int)sum;
    }
};
#endif
